#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Solution {
public:
	vector<int> dailyTemperatures2(vector<int>& temperatures) {
		vector<int> res;
		for (int i = 0; i < temperatures.size(); i++) {
			int day = temperatures[i];
			bool flag = false;
			for (int j = i + 1; j < temperatures.size(); j++) {
				if (temperatures[j] > temperatures[i]) {
					flag = true;
					res.push_back(j - i);
					break;
				}
			}
			if (!flag) res.push_back(0);
		}
		return res;
	}

	vector<int> dailyTemperatures(vector<int>& temperatures) {
		int cap = temperatures.size();
		vector<int> ans(cap,0);
		stack<int> stk;
		for (int i = 0; i < cap; i++) {
			while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
				int prevIn = stk.top();
				ans[prevIn] = i - prevIn;
				stk.pop();
			}
			stk.push(i);
		}
		return ans;
	}
};

void main() {
	vector<int> temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };
	Solution s;
	s.dailyTemperatures(temperatures);
}